package com.javaDemo.ti;

/**
 * @ClassName: Zuichanghuiwenzichuan
 * @Auther: chenshiyue
 * @Date: 2020/5/17 01:37
 * @Description:
 */
public class Zuichanghuiwenzichuan {
    public static String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        int strLen = s.length();
        int maxStart = 0;  //最长回文串的起点
        int maxEnd = 0;    //最长回文串的终点
        int maxLen = 1;  //最长回文串的长度

        boolean[][] dp = new boolean[strLen][strLen];

        for (int r = 1; r < strLen; r++) {
            for (int l = 0; l < r; l++) {
                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[r - 1][l + 1])) {
                    dp[l][r] = true;
                    if (r - l + 1 > maxLen) {
                        maxLen = r - l + 1;
                        maxStart = l;
                        maxEnd = r;

                    }
                }

            }

        }
        return s.substring(maxStart, maxEnd + 1);

    }

    public static void main(String[] args) {
        // String a="ababaa";
        // System.out.println(zhongxinkuosan(a));
        int a=2^24^2;
        System.out.println(a);
    }
    static int count=0;
    static String resultStr="";
    private static String zhongxinkuosan(String s) {
        if(s.length()<=1){
            return s;
        }
        for(int i=0;i<s.length()-1;i++){
            judjement(s,i,i);
            judjement(s,i,i+1);
        }
        return resultStr;
    }

    private static void judjement(String s, int left, int right) {
        while(left>=0&&right<s.length()){
            if(s.charAt(left)==s.charAt(right)){
                if(right-left+1>count){
                    count=right-left+1;
                    resultStr=s.substring(left,right+1);
                }
                left--;
                right++;
            }else{
                break;
            }
        }
    }

    /**
     * 中心扩散
     * @param s
     * @return
     */
    public String longestPalindromez(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        int maxLen = 1;
        String res = s.substring(0, 1);
        // 中心位置枚举到 len - 2 即可
        for (int i = 0; i < len - 1; i++) {
            String oddStr = centerSpread(s, i, i);
            String evenStr = centerSpread(s, i, i + 1);
            String maxLenStr = oddStr.length() > evenStr.length() ? oddStr : evenStr;
            if (maxLenStr.length() > maxLen) {
                maxLen = maxLenStr.length();
                res = maxLenStr;
            }
        }
        return res;
    }

    private String centerSpread(String s, int left, int right) {
        // left = right 的时候，此时回文中心是一个字符，回文串的长度是奇数
        // right = left + 1 的时候，此时回文中心是一个空隙，回文串的长度是偶数
        int len = s.length();
        int i = left;
        int j = right;
        while (i >= 0 && j < len) {
            if (s.charAt(i) == s.charAt(j)) {
                i--;
                j++;
            } else {
                break;
            }
        }
        // 这里要小心，跳出 while 循环时，恰好满足 s.charAt(i) != s.charAt(j)，因此不能取 i，不能取 j
        return s.substring(i + 1, j);
    }


}
